#include <stdio.h>
#include <stdlib.h>

//定义最大顶点数，本常量在定义MGraph结构体的顶点和边时，都必须被用到
#define MaxVertexNum 100
typedef enum{FALSE,TRUE} Boolean;

typedef struct{
    // 定义本结构体的具体内容
    char vexs[MaxVertexNum];//节点表
    int  arcs[MaxVertexNum][MaxVertexNum];//邻接矩阵，边表
//  int vexnum,arcnum;//顶点数和边数

} MGraph;

// ====查找图G的顶点的编号====
// 编号为构建图G时每个顶点的读入顺序，从0开始。
// 查找到指定顶点名字时，返回对应编号；找不到时，返回-1 。
int locate_vertex(MGraph * G, char vertex_name) {
    for (int i = 0; i < 8; i++) {
        if (G->vexs[i]==vertex_name){
            return i;
        }
    }
    return -1;
}

//=========建立邻接矩阵=======
// 参数 G_pp 是尚未被初始化的 (指向 (指向 MGraph 的指针) 的指针)
// 参数 graph_data_filename 是存储如下格式的图数据的文件名（字符串）：
/*
 * 顶点数 边数
 * 顶点名字序列（用a b c d e 等字符命名）
 * a b // 边1
 * a c // 边2
 * d e // 边3
 */
void create_graph(MGraph ** G_pp, char * graph_data_filename)
{
  FILE * fp;
  size_t len = 0;
  ssize_t read;
  int num_nodes, num_edges;

  fp = fopen(graph_data_filename, "r");
//  rewind(fp);
  if (fp == NULL) {
      printf("文件读取失败!!!");
      exit(EXIT_FAILURE);
  }

  fscanf(fp, "%d %d\n", &num_nodes, &num_edges);
  printf("节点数：%d \n边数：%d\n",num_nodes,num_edges);

  int i,j;
  // 实现开始：可以自行定义变量，但是不要删掉或者更改对fopen和fclose的调用
    // 如上，用fscanf从fp里读取字符
  *G_pp = (MGraph *)malloc(sizeof(MGraph));
  MGraph *gpp = *G_pp;
    for (i = 0; i < num_nodes; i++) {
        gpp->vexs[i]=fgetc(fp);
        fgetc(fp);
        printf("%c ",gpp->vexs[i]);
    }
    printf("\n");
    //初始化邻接矩阵
    for (i = 0; i < num_nodes; i++) {
        for (j = 0; j < num_nodes; ++j) {
            gpp->arcs[i][j]=0;
        }
    }
    char jd1,jd2;
    for (int k = 0; k < num_edges; k++) {
        jd1 = fgetc(fp);
        printf("%c",jd1);
        fgetc(fp);
        jd2 = fgetc(fp);
        fgetc(fp);
        printf("%c\n",jd2);
        for (i = 0; i < num_nodes; i++) {
            for (j = 0; j < num_nodes; j++) {
                if (gpp->vexs[j]==jd2&&gpp->vexs[i]==jd1){
                    gpp->arcs[i][j]=1;
                    gpp->arcs[j][i]=1;
                }
            }
        }
    }
    //输出邻接矩阵
    printf("邻接矩阵如下：\n");
    for (i = 0; i < num_edges; i++) {
        for (j = 0; j < num_edges; j++) {
            printf("%d\t",gpp->arcs[i][j]);
        }
        printf("\n");
    }
  // 实现结束
  fclose(fp);
}
//========dfs：深度优先遍历的递归算法======
// 参数 G：指向MGraph的指针
// 参数 i: 从i个顶点开始深度优先遍历。i是顶点在原始数据中 顶点名字序列 里从0开始的位置；比如顶点 b 在 顶点序列 a b c d e f中的位置是 1。
// 参数 visited_order: 当前顶点被访问的全局顺序
// 参数 result_sequence: 用于记录在 当全局访问顺序为 visited_order 时，被访问的结点名字（字符）
void dfs(MGraph *G, int i, Boolean visited[], char * result_sequence, int * visited_order)
{
    int j;
    //   printf("%c",G->vexs[i]);     //访问顶点Vi
    result_sequence[*visited_order]=G->vexs[i];
    *visited_order=*visited_order+1;
    visited[i]=TRUE;             //置已访问标志
    for(j=0;j<8;j++){//依次搜索Vi的邻接点
        if(G->arcs[i][j]==1 && ! visited[j]){
            dfs(G,j,visited,result_sequence,visited_order);  //（Vi，Vj）∈E，且Vj未访问过，故Vj为新出发点
        }
    }
}

//===========bfs：广度优先遍历=======
// 参数 G：指向MGraph的指针
// 参数 k: 从k个顶点开始深度优先遍历。k是顶点在原始数据中 顶点名字序列 里从0开始的位置；比如顶点 b 在 顶点序列 a b c d e f中的位置是 1。
// 参数 visited_sequence: 用于记录在广度优先遍历时，依次被访问的顶点的名字
void bfs(MGraph *G, int k, Boolean visited[], char * visited_sequence)
{
    int i,j=0,r=0,f=0;
    char dl[MaxVertexNum];
    //初始化所有顶点设置为未被访问
    for(i=0; i<MaxVertexNum; i++) {
        visited[i] = FALSE;
        visited_sequence[i]=0;
        dl[i]=0;
    }
    dl[r]=G->vexs[k];
    visited[k]=TRUE;
    while (dl[r]!= 0){
        for (i = 0; i < 8; i++) {
            if (G->arcs[k][i]==1&&visited[i]==FALSE){
                f++;
                visited[i]=TRUE;
                dl[f]=G->vexs[i];
            }
        }
        visited_sequence[j]=dl[r];
        r++;
        k=locate_vertex(G,dl[r]);
        j++;
    }
}

//==========main=====
void main()
{
    int i;
    MGraph *G;
    Boolean visited[MaxVertexNum];

    for(i=0; i<MaxVertexNum; i++) {
        visited[i] = FALSE;
    }

    create_graph(&G, "graph_data.txt"); //建立邻接矩阵

    char dfs_sequence[MaxVertexNum] = {'\0'};
    int visited_order = 0;
    dfs(G, 0, visited, dfs_sequence, &visited_order); //深度优先遍历。 应该输出：abdhecfg
    printf("Print Graph DFS: ");
    printf("%s\n", dfs_sequence);
    printf("\n");

    for(i=0; i<MaxVertexNum; i++) {
        visited[i] = FALSE;
    }
    char bfs_sequence[MaxVertexNum] = {'\0'};
    bfs(G, 0, visited, bfs_sequence); //以序号为3的顶点开始广度优先遍历。应该输出：abcdefgh
    printf("Print Graph BFS: ");
    printf("%s\n", bfs_sequence);

    char bfs_sequence2[MaxVertexNum] = {'\0'};
    bfs(G, 3, visited, bfs_sequence2); //以序号为3的顶点开始广度优先遍历。应该输出：dbhaecfg
    printf("Print Graph BFS: ");
    printf("%s\n", bfs_sequence2);
}
